package leetcode.editor.cn;
//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 
//
// 返回这三个数的和。 
//
// 假定每组输入只存在恰好一个解。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,0], target = 1
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 1000 
// -1000 <= nums[i] <= 1000 
// -10⁴ <= target <= 10⁴ 
// 
//
// Related Topics 数组 双指针 排序 👍 1565 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution255 {


    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int start = i + 1, end = nums.length - 1;
            while (start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if (Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if (sum > target)
                    end--;
                else if (sum < target)
                    start++;
                else
                    return ans;
            }
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }

    public int threeSumClosest1(int[] nums, int target) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int sum = two(nums, i, target, num);
            int tem = Math.abs(target - sum);
            if (tem == 0) return sum;
            if (tem < min) {
                min = tem;
                res = sum;
            }
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }

    private int two(int[] nums, int index, int target, int num) {
        int l = index + 1;
        int r = nums.length - 1;
        int left;
        int right;
        int sub = Integer.MAX_VALUE;
        int res = Integer.MAX_VALUE;
        while (l < r) {
            left = nums[l];
            right = nums[r];
            int sum = num + left + right;
            int tem = Math.abs(target - sum);
            if (tem == 0) return sum;
            if (tem < sub) {
                sub = tem;
                res = sum;
            }

            if (r - l > 1 && Math.abs(target - (nums[l + 1] + right + num)) < Math.abs(target - (nums[r - 1] + left + num))) {
                l++;
            } else {
                r--;
            }


        }
        return res;
    }

    public static void main(String[] args) {
        Solution255 s = new Solution255();
        System.out.println(s.threeSumClosest(new int[]{2, 5, 6, 7}, 16));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
